package com.lw.leetcode.sort.c;

import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/20 9:27
 */
public class RangeModule {

    public static void main(String[] args) {
        RangeModule test = new RangeModule();


        // [null,null,null,null,true,false,false,null,false]
        test.addRange(10, 180);
        System.out.println(test.map);
        test.addRange(150, 200);
        System.out.println(test.map);
        test.addRange(250, 500);
        System.out.println(test.map);
        System.out.println(test.queryRange(50, 100));
        System.out.println(test.queryRange(180, 300));
        System.out.println(test.queryRange(600, 1000));
        test.removeRange(50, 150);
        System.out.println(test.map);
        System.out.println(test.queryRange(50, 100));


        // [null,null,null,null,null,null,null,true,true,true]
//        test.addRange(6,8);
//        System.out.println(test.map);
//        test.removeRange(7,8);
//        System.out.println(test.map);
//        test.removeRange(8,9);
//        System.out.println(test.map);
//        test.addRange(8,9);
//        System.out.println(test.map);
//        test.removeRange(1,3);
//        System.out.println(test.map);
//        test.addRange(1,8);
//        System.out.println(test.map);
//        System.out.println(test.queryRange(2,4));
//        System.out.println(test.queryRange(2,9));
//        System.out.println(test.queryRange(4,6));

        // [null,null,null,false,null,true,null,null,true,null]
//        test.addRange(5,6);
//        System.out.println(test.map);
//        test.addRange(2,8);
//        System.out.println(test.map);
//        System.out.println(test.queryRange(1,4));
//        test.removeRange(2,4);
//        System.out.println(test.map);
//        System.out.println(test.queryRange(4,5));
//        test.removeRange(4,6);
//        System.out.println(test.map);
//        test.addRange(5,9);
//        System.out.println(test.map);
//        System.out.println(test.queryRange(5,6));
//        test.removeRange(6,7);
//        System.out.println(test.map);
    }

    private TreeMap<Integer, Integer> map = new TreeMap<>();

    public RangeModule() {

    }

    public void addRange(int left, int right) {
        right--;
        Map.Entry<Integer, Integer> entry = map.floorEntry(left);
        if (entry != null && entry.getValue() >= left - 1) {
            int value = entry.getValue();
            if (value >= right) {
                return;
            }
            left = entry.getKey();
        }
        entry = map.ceilingEntry(left + 1);
        if (entry == null) {
            map.put(left, right);
            return;
        }
        while (entry != null) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (key > right + 1) {
                map.put(left, right);
                break;
            }
            map.remove(key);
            if (value >= right) {
                right = value;
                break;
            }
            entry = map.ceilingEntry(left + 1);
        }
        map.put(left, right);

    }

    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = map.floorEntry(left);
        return (entry != null && entry.getKey() <= left && entry.getValue() >= right - 1);
    }

    public void removeRange(int left, int right) {
        right--;
        Map.Entry<Integer, Integer> entry = map.floorEntry(left);

        if (entry != null) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (value >= left) {
                if (key == left) {
                    map.remove(key);
                } else {
                    map.put(key, left - 1);
                }
                if (value > right) {
                    map.put(right + 1, value);
                    return;
                }
            }

        }

        entry = map.ceilingEntry(left);
        while (entry != null) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (key > right) {
                break;
            }
            map.remove(key);
            if (value > right) {
                map.put(right + 1, value);
            }
            entry = map.ceilingEntry(left);
        }
    }
}
